package leetcode.recursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//47. 全排列 II
public class PermuteUnique {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backtrace(res, path, used, nums, 0, nums.length);
        return res;
    }

    private void backtrace(List<List<Integer>> res, List<Integer> path,
                           boolean[] used, int[] nums, int start, int length) {
        if (start == length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }

            used[i] = true;
            path.add(nums[i]);
            backtrace(res, path, used, nums, start + 1, length);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    // 二战全排列II 含有重复数字
    public List<List<Integer>> permuteUniqueP(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int n = nums.length;
        boolean[] used = new boolean[n];
        // 由于有重复数据，所以需要先排序
        Arrays.sort(nums);
        backtracing(res, path, nums, 0, n, used);
        return res;
    }

    private void backtracing(List<List<Integer>> res, List<Integer> path,
                             int[] nums, int start, int n, boolean[] used) {
        if (start == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            // 判断是否是重复,used[i]确保自己不重复使用
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracing(res, path, nums, start + 1, n, used);
            // 回溯
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
